import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class L94_2 {

    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            if (root == null) {
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode node = root;
            while (node != null || !stack.isEmpty()) {
                if (node != null) {
                    stack.push(node);
                    node = node.left;
                } else {
                    node = stack.pop();
                    list.add(node.val);
                    node = node.right;
                }
            }
            return list;
        }
    }
}
